#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
#include<queue>
using namespace std;

struct TreeNode {
	int val;
	TreeNode* left;
	TreeNode* right;
	
};
vector<vector<int>> levelOrderBottom(TreeNode* root) {
    vector<vector<int>> vv;
    queue<TreeNode*> q1;
    queue<TreeNode*> q2;
    q1.push(root);
    while (!q1.empty() || !q2.empty())
    {
        vector<int> v;
        while (!q1.empty()) {
            TreeNode* tmp = q1.front();
            if (tmp->left != nullptr) {
                q2.push(tmp->left);
            }
            if (tmp->right != nullptr) {
                q2.push(tmp->right);
            }
            q1.pop();
            v.push_back(tmp->val);
        }
        while (!q2.empty()) {
            q1.push(q2.front());
            q2.pop();
        }
        vv.push_back(v);
    }
    reverse(vv.begin(), vv.end());
    return vv;
}
int main() {
    TreeNode n1, n2, n3, n4, n5;
    n1.val = 3; n2.val = 9;
    n3.val = 20; n4.val = 15;
    n5.val = 7;
    n1.left = &n2; n1.right = &n3;
    n2.left = n2.right = nullptr;
    n3.left = &n4; n3.right = &n5;
    n4.left = n4.right = nullptr;
    n5.left = n5.right = nullptr;
    levelOrderBottom(&n1);
    return 0;
}